/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-10-06
 * Time: 20:52
 */

public class Solution {
    // 二分查找
    public int shipWithinDays(int[] weights, int days) {
        // 左边界为 物品重量的最大值
        // 右边界为物品重量总和
        int max = 0;
        int sum = 0;
        for (int weight: weights) {
            max = Math.max(max, weight);
            sum += weight;
        }
        int left = max;
        int right = sum;
        while (left < right) {
            int mid = ((right-left)>>1) + left;
            if (!judge(weights, days, mid)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private boolean judge(int[] weights, int days, int capacity) {
        int sum = 0;
        int day = 1;
        for (int weight: weights) {
            sum += weight;
            if (sum > capacity) {
                sum = weight;
                day++;
            }
        }
        return day <= days;
    }
}
